{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Longest Consecutive Sequence II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestConsecutive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树中最长的连续序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定二叉树的根&nbsp;<code>root</code>&nbsp;，返回树中<strong>最长连续路径</strong>的长度。<br />\n",
    "<strong>连续路径</strong>是路径中相邻节点的值相差 <code>1</code> 的路径。此路径可以是增加或减少。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，&nbsp;<code>[1,2,3,4]</code> 和 <code>[4,3,2,1]</code> 都被认为有效，但路径 <code>[1,2,4,3]</code> 无效。</li>\n",
    "</ul>\n",
    "\n",
    "<p>另一方面，路径可以是子-父-子顺序，不一定是父子顺序。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/14/consec2-1-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [1,2,3]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 最长的连续路径是 [1, 2] 或者 [2, 1]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/14/consec2-2-tree.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>root = [2,1,3]\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释:</strong> 最长的连续路径是 [1, 2, 3] 或者 [3, 2, 1]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树上所有节点的值都在&nbsp;<code>[1, 3 * 10<sup>4</sup>]</code>&nbsp;范围内。</li>\n",
    "\t<li><code>-3 * 10<sup>4</sup>&nbsp;&lt;= Node.val &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-longest-consecutive-sequence-ii](https://leetcode.cn/problems/binary-tree-longest-consecutive-sequence-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-longest-consecutive-sequence-ii](https://leetcode.cn/problems/binary-tree-longest-consecutive-sequence-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[2,1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        maxval = 0\n",
    "        def helper(node):\n",
    "            nonlocal maxval\n",
    "            returnval = [1, 1] # 0-th index is increasing length, 1-st index is decreasing length\n",
    "            if node.left:\n",
    "                leftval = helper(node.left)\n",
    "                if node.val + 1 == node.left.val: # up to down increasing\n",
    "                    returnval[0] = leftval[0] + 1\n",
    "                elif node.val - 1 == node.left.val: # up to down decreasing\n",
    "                    returnval[1] = leftval[1] + 1\n",
    "            if node.right:\n",
    "                rightval = helper(node.right)\n",
    "                if node.val + 1 == node.right.val:\n",
    "                    if rightval[0] + 1 > returnval[0]:\n",
    "                        returnval[0] = rightval[0] + 1\n",
    "                elif node.val - 1 == node.right.val:\n",
    "                    if rightval[1] + 1 > returnval[1]:\n",
    "                        returnval[1] = rightval[1] + 1\n",
    "            maxval = max(maxval, returnval[0] + returnval[1] - 1)\n",
    "            return returnval\n",
    "        \n",
    "        helper(root)\n",
    "        return maxval\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        res = 0\n",
    "        def dfs(root, prev):\n",
    "            # 以root为根的子树，返回最长的以root为结尾的递增和递减链条\n",
    "            nonlocal res\n",
    "\n",
    "            if root is None:\n",
    "                return 0, 0\n",
    "\n",
    "            left_inc, left_dec = dfs(root.left, root.val)\n",
    "            right_inc, right_dec = dfs(root.right, root.val)\n",
    "\n",
    "            len1 = left_inc + 1 + right_dec\n",
    "            len2 = left_dec + 1 + right_inc\n",
    "            res = max(res, len1, len2)\n",
    "\n",
    "            if root.val == prev + 1:\n",
    "                # 3  <- 2\n",
    "                return 0, max(left_dec, right_dec) + 1\n",
    "            elif root.val == prev - 1:\n",
    "                # 2 <- 3\n",
    "                return max(left_inc, right_inc) + 1, 0\n",
    "            else:\n",
    "                return 0, 0\n",
    "        \n",
    "        dfs(root, -100000)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        def longest_path(root):\n",
    "            nonlocal maxval\n",
    "            if not root:\n",
    "                return [0, 0]\n",
    "            \n",
    "            inr = dcr = 1\n",
    "            if root.left:\n",
    "                left = longest_path(root.left)\n",
    "                if (root.val == root.left.val + 1):\n",
    "                    dcr = left[1] + 1\n",
    "                elif (root.val == root.left.val - 1):\n",
    "                    inr = left[0] + 1\n",
    "            \n",
    "            if root.right:\n",
    "                right = longest_path(root.right)\n",
    "                if (root.val == root.right.val + 1):\n",
    "                    dcr = max(dcr, right[1] + 1)\n",
    "                elif (root.val == root.right.val - 1):\n",
    "                    inr = max(inr, right[0] + 1)\n",
    "                    \n",
    "            maxval = max(maxval, dcr + inr - 1)\n",
    "            return [inr, dcr]\n",
    "       \n",
    "        maxval = 0\n",
    "        longest_path(root)\n",
    "        return maxval\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def longest_path(root):\n",
    "            nonlocal maxval\n",
    "\n",
    "            if not root:\n",
    "                return [0, 0]\n",
    "\n",
    "            inr = dcr = 1\n",
    "            if root.left:\n",
    "                left = longest_path(root.left)\n",
    "                if root.val == root.left.val + 1:\n",
    "                    dcr = left[1] + 1\n",
    "                elif root.val == root.left.val - 1:\n",
    "                    inr = left[0] + 1\n",
    "                \n",
    "            if root.right:\n",
    "                right = longest_path(root.right)\n",
    "                if root.val == root.right.val + 1:\n",
    "                    dcr = max(dcr, right[1] + 1)\n",
    "                elif root.val == root.right.val - 1:\n",
    "                    inr = max(inr, right[0] + 1)\n",
    "\n",
    "            maxval = max(maxval, dcr + inr - 1)\n",
    "            return [inr, dcr]\n",
    "\n",
    "        maxval = 0\n",
    "        longest_path(root)\n",
    "        return maxval\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            nonlocal max_len\n",
    "\n",
    "            if not root: return [0, 0]\n",
    "\n",
    "            inc = dec = 1\n",
    "            if root.left:\n",
    "                left = dfs(root.left)\n",
    "                if root.val == root.left.val + 1:\n",
    "                    dec = left[1] + 1\n",
    "                elif root.val == root.left.val - 1:\n",
    "                    inc = left[0] + 1\n",
    "            \n",
    "            if root.right:\n",
    "                right = dfs(root.right)\n",
    "                if root.val == root.right.val + 1:\n",
    "                    dec = max(dec, right[1] + 1)\n",
    "                elif root.val == root.right.val - 1:\n",
    "                    inc = max(inc, right[0] + 1)\n",
    "            \n",
    "            max_len = max(max_len, inc + dec - 1)\n",
    "            return [inc, dec]\n",
    "\n",
    "        \n",
    "        max_len = 0\n",
    "        dfs(root)\n",
    "        return max_len\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        anw = 0\n",
    "        def dfs(node):\n",
    "            nonlocal anw\n",
    "            if not node:\n",
    "                return [0,0]\n",
    "\n",
    "            cur_inc = cur_dec = 1\n",
    "\n",
    "            if node.left:\n",
    "                left = dfs(node.left)\n",
    "                if node.val == node.left.val + 1:\n",
    "                    cur_dec = left[1] + 1\n",
    "                elif node.val == node.left.val - 1:\n",
    "                    cur_inc = left[0] + 1\n",
    "            \n",
    "            if node.right:\n",
    "                right = dfs(node.right)\n",
    "                if node.val == node.right.val + 1:\n",
    "                    cur_dec = max(cur_dec, right[1] + 1)\n",
    "                elif node.val == node.right.val - 1:\n",
    "                    cur_inc = max(cur_inc, right[0] + 1)\n",
    "        \n",
    "            anw = max(anw, cur_inc + cur_dec - 1)\n",
    "            return [cur_inc, cur_dec]\n",
    "        \n",
    "        dfs(root)\n",
    "        return anw\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        maxval = 0\n",
    "        def helper(node):\n",
    "            nonlocal maxval\n",
    "            if node is None:\n",
    "                return [0, 0]\n",
    "                \n",
    "            returnval = [1, 1] # 0-th index is increasing length, 1-st index is decreasing length\n",
    "            if node.left:\n",
    "                leftval = helper(node.left)\n",
    "                if node.val + 1 == node.left.val: # up to down increasing\n",
    "                    returnval[0] = leftval[0] + 1\n",
    "                elif node.val - 1 == node.left.val: # up to down decreasing\n",
    "                    returnval[1] = leftval[1] + 1\n",
    "            if node.right:\n",
    "                rightval = helper(node.right)\n",
    "                if node.val + 1 == node.right.val:\n",
    "                    if rightval[0] + 1 > returnval[0]:\n",
    "                        returnval[0] = rightval[0] + 1\n",
    "                elif node.val - 1 == node.right.val:\n",
    "                    if rightval[1] + 1 > returnval[1]:\n",
    "                        returnval[1] = rightval[1] + 1\n",
    "            maxval = max(maxval, returnval[0] + returnval[1] - 1)\n",
    "            return returnval\n",
    "        \n",
    "        helper(root)\n",
    "        return maxval\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        def longPath(root: Optional[TreeNode]) -> List[int]:\n",
    "            nonlocal res\n",
    "            if not root: return [0,0]\n",
    "            dec,inc = 1,1\n",
    "            if root.left:\n",
    "                left = longPath(root.left)\n",
    "                if root.val == root.left.val+1: dec = max(dec,left[0]+1)\n",
    "                elif root.val+1 == root.left.val: inc = max(inc,left[1]+1)\n",
    "            if root.right:\n",
    "                right = longPath(root.right)\n",
    "                if root.val == root.right.val+1: dec = max(dec,right[0]+1)\n",
    "                elif root.val+1 == root.right.val: inc = max(inc,right[1]+1)\n",
    "            res = max(res,inc+dec-1)\n",
    "            return [dec,inc]\n",
    "\n",
    "        res = 0 \n",
    "        longPath(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def longestConsecutive(self, root: TreeNode) -> int:\n",
    "               \n",
    "       def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "       maxval = 0\n",
    "       longest_path(root)\n",
    "       return maxval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "       def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "       maxval = 0\n",
    "       longest_path(root)\n",
    "       return maxval\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        maxL = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return [1, 1]\n",
    "            \n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "\n",
    "            if node.left:\n",
    "                # 左上升\n",
    "                if node.val == node.left.val + 1:\n",
    "                    left[0] += 1\n",
    "                else:\n",
    "                    left[0] = 1\n",
    "                # 左下降\n",
    "                if node.val == node.left.val - 1:\n",
    "                    left[1] += 1\n",
    "                else:\n",
    "                    left[1] = 1\n",
    "            if node.right:\n",
    "                # 右上升\n",
    "                if node.val == node.right.val + 1:\n",
    "                    right[0] += 1\n",
    "                else:\n",
    "                    right[0] = 1\n",
    "                # 右下降\n",
    "                if node.val == node.right.val - 1:\n",
    "                    right[1] += 1\n",
    "                else:\n",
    "                    right[1] = 1\n",
    "            nonlocal maxL\n",
    "            maxL = max(maxL, left[0] + right[1]-1, left[1] + right[0]-1)\n",
    "            return [max(left[0], right[0]), max(left[1], right[1])]\n",
    "\n",
    "        dfs(root)\n",
    "        return maxL\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def longest_path(root):\n",
    "            nonlocal max_val\n",
    "\n",
    "            if not root:\n",
    "                return [0, 0]\n",
    "\n",
    "            inr, dcr = 1, 1\n",
    "            if root.left:\n",
    "                left = longest_path(root.left)\n",
    "                if root.val == root.left.val + 1:\n",
    "                    dcr = left[1] + 1\n",
    "                elif root.val == root.left.val - 1:\n",
    "                    inr = left[0] + 1\n",
    "            \n",
    "            if root.right:\n",
    "                right = longest_path(root.right)\n",
    "                if root.val == root.right.val + 1:\n",
    "                    dcr = max(dcr, right[1] + 1)\n",
    "                elif root.val == root.right.val - 1:\n",
    "                    inr = max(inr, right[0] + 1)\n",
    "\n",
    "            max_val = max(max_val, dcr + inr - 1)\n",
    "            return [inr, dcr]\n",
    "            \n",
    "        max_val = 0\n",
    "        longest_path(root)\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            nonlocal max_len\n",
    "\n",
    "            if not root: return [0, 0]\n",
    "\n",
    "            inc = dec = 1\n",
    "            left = dfs(root.left)\n",
    "            right = dfs(root.right)\n",
    "            if root.left:\n",
    "                if root.val == root.left.val + 1:\n",
    "                    dec = left[1] + 1\n",
    "                elif root.val == root.left.val - 1:\n",
    "                    inc = left[0] + 1\n",
    "            \n",
    "            if root.right:\n",
    "                if root.val == root.right.val + 1:\n",
    "                    dec = max(dec, right[1] + 1)\n",
    "                elif root.val == root.right.val - 1:\n",
    "                    inc = max(inc, right[0] + 1)\n",
    "            \n",
    "            max_len = max(max_len, inc + dec - 1)\n",
    "            return [inc, dec]\n",
    "\n",
    "        \n",
    "        max_len = 0\n",
    "        dfs(root)\n",
    "        return max_len\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 1, 1\n",
    "            # - +\n",
    "            lmin, lmax = dfs(root.left)\n",
    "            rmin, rmax = dfs(root.right)\n",
    "            tmin, tmax = 1, 1\n",
    "            if root.left and abs(root.val - root.left.val) == 1:\n",
    "                if root.left.val > root.val:\n",
    "                    tmin = lmin + 1\n",
    "                else:\n",
    "                    tmax = lmax + 1\n",
    "            if root.right and abs(root.val - root.right.val) == 1:\n",
    "                if root.right.val > root.val:\n",
    "                    tmin = max(tmin, rmin + 1)\n",
    "                else:\n",
    "                    tmax = max(tmax, rmax + 1)\n",
    "\n",
    "            temp = 0\n",
    "            if root.left and root.right:\n",
    "                if root.left.val + 1 == root.val == root.right.val - 1:\n",
    "                    temp = lmax + rmin + 1\n",
    "                if root.left.val - 1 == root.val == root.right.val + 1:\n",
    "                    temp = lmin + rmax + 1\n",
    "            self.ans = max((self.ans, temp, tmin, tmax))\n",
    "            return tmin, tmax\n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        res=0\n",
    "        def dfs(r):\n",
    "            if not r:return 0,0,-1000000\n",
    "            la,lj,lv=dfs(r.left)\n",
    "            ra,rj,rv=dfs(r.right)\n",
    "            a,j=1,1\n",
    "            if lv==r.val+1:a=max(a,la+1)\n",
    "            if rv==r.val+1:a=max(a,ra+1)\n",
    "            if lv==r.val-1:j=max(j,lj+1)\n",
    "            if rv==r.val-1:j=max(j,rj+1)\n",
    "            nonlocal res\n",
    "            if lv+1==r.val and r.val+1==rv:\n",
    "                res=max(res,lj+1+ra)\n",
    "            if lv-1==r.val and r.val-1==rv:\n",
    "                res=max(res,la+1+rj)\n",
    "            res=max(res,a,j)\n",
    "            return a,j,r.val\n",
    "        dfs(root)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(root: Optional[TreeNode], dir: int):\n",
    "            # given the root, and orientation\n",
    "            # return maxLen, starting from root\n",
    "            if not root:\n",
    "                return 0\n",
    "            l1 = dfs(root.left, dir)\n",
    "            r1 = dfs(root.right, dir)\n",
    "            cand1, cand2 = 1, 1\n",
    "            if l1 and root.left.val - root.val == dir:\n",
    "                cand1 += l1\n",
    "            if r1 and root.right.val - root.val == dir:\n",
    "                cand2 += r1\n",
    "            return max(cand1,cand2)\n",
    "\n",
    "        def search(root: Optional[TreeNode]):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return 0\n",
    "            inc = dfs(root,1)\n",
    "            dec = dfs(root,-1)\n",
    "            res = max(res,inc+dec-1)\n",
    "            search(root.left)\n",
    "            search(root.right)\n",
    "        search(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self._max_length = 0\n",
    "\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.answer_1(root)\n",
    "\n",
    "    def answer_1(self, root):\n",
    "        self._dfs_1(root)\n",
    "        return self._max_length\n",
    "\n",
    "    def _dfs_1(self, node):\n",
    "        if not node:\n",
    "            return 0, 0\n",
    "\n",
    "        left_up, left_down = self._dfs_1(node.left)\n",
    "        right_up, right_down = self._dfs_1(node.right)\n",
    "\n",
    "        new_up = new_down = 1\n",
    "\n",
    "        if node.left and node.left.val + 1 == node.val:\n",
    "            new_up = max(new_up, left_up + 1)\n",
    "        if node.left and node.left.val - 1 == node.val:\n",
    "            new_down = max(new_down, left_down + 1)\n",
    "\n",
    "        if node.right and node.right.val + 1 == node.val:\n",
    "            new_up = max(new_up, right_up + 1)\n",
    "\n",
    "        if node.right and node.right.val - 1 == node.val:\n",
    "            new_down = max(new_down, right_down + 1)\n",
    "\n",
    "        self._max_length = max(self._max_length, new_up + new_down - 1)\n",
    "        return new_up, new_down"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, [], []\n",
    "\n",
    "            ll, linc, ldec = dfs(node.left)\n",
    "            rl, rinc, rdec = dfs(node.right)\n",
    "\n",
    "            ret = max(ll, rl)\n",
    "            if linc and rdec and node.val == linc[0] - 1 == rdec[0] + 1:\n",
    "                ret = max(ret, len(linc) + 1 + len(rdec))\n",
    "            elif rinc and ldec and node.val == rinc[0] - 1 == ldec[0] + 1:\n",
    "                ret = max(ret, len(rinc) + 1 + len(ldec))\n",
    "            if (not linc or node.val == linc[0] - 1):\n",
    "                linc = [node.val] + linc\n",
    "            else:\n",
    "                linc = [node.val]\n",
    "            if (not ldec or node.val == ldec[0] + 1):\n",
    "                ldec = [node.val] + ldec\n",
    "            else:\n",
    "                ldec= [node.val]\n",
    "            if (not rinc or node.val == rinc[0] - 1):\n",
    "                rinc = [node.val] + rinc\n",
    "            else:\n",
    "                rinc= [node.val]\n",
    "            if (not rdec or node.val == rdec[0] + 1):\n",
    "                rdec = [node.val] + rdec\n",
    "            else:\n",
    "                rdec = [node.val]\n",
    "\n",
    "            return max(ret, len(linc), len(ldec), len(rinc), len(rdec)), linc if len(linc) > len(rinc) else rinc, ldec if len(ldec) > len(rdec) else rdec\n",
    "        \n",
    "        l, x, y = dfs(root)\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root: Optional[TreeNode]) -> Tuple[int, int]:\n",
    "        if not root:\n",
    "            return 0, 0\n",
    "        left_incs, left_decs = self.dfs(root.left)\n",
    "        right_incs, right_decs = self.dfs(root.right)\n",
    "        root_incs, root_decs = 1, 1\n",
    "        if root.left:\n",
    "            if root.left.val == root.val + 1:\n",
    "                root_incs += left_incs\n",
    "            elif root.left.val == root.val - 1:\n",
    "                root_decs += left_decs\n",
    "        if root.right:\n",
    "            if root.right.val == root.val + 1:\n",
    "                root_incs = max(root_incs, right_incs + 1)\n",
    "            elif root.right.val == root.val - 1:\n",
    "                root_decs = max(root_decs, right_decs + 1)\n",
    "        self.res = max(self.res, root_incs + root_decs - 1)\n",
    "        return root_incs, root_decs\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res: int = 0\n",
    "        self.dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def longestConsecutive(self, root: TreeNode) -> int:\n",
    "               \n",
    "       def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "       maxval = 0\n",
    "       longest_path(root)\n",
    "       return maxval\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, [], []\n",
    "\n",
    "            ll, linc, ldec = dfs(node.left)\n",
    "            rl, rinc, rdec = dfs(node.right)\n",
    "\n",
    "            ret = max(ll, rl)\n",
    "            if linc and rdec and node.val == linc[0] - 1 == rdec[0] + 1:\n",
    "                ret = max(ret, len(linc) + 1 + len(rdec))\n",
    "            if rinc and ldec and node.val == rinc[0] - 1 == ldec[0] + 1:\n",
    "                ret = max(ret, len(rinc) + 1 + len(ldec))\n",
    "            if (not linc or node.val == linc[0] - 1):\n",
    "                linc = [node.val] + linc\n",
    "                ret = max(ret, len(linc))\n",
    "            else:\n",
    "                linc = [node.val]\n",
    "            if (not ldec or node.val == ldec[0] + 1):\n",
    "                ldec = [node.val] + ldec\n",
    "                ret = max(ret, len(ldec))\n",
    "            else:\n",
    "                ldec= [node.val]\n",
    "            if (not rinc or node.val == rinc[0] - 1):\n",
    "                rinc = [node.val] + rinc\n",
    "                ret = max(ret, len(rinc))\n",
    "            else:\n",
    "                rinc= [node.val]\n",
    "            if (not rdec or node.val == rdec[0] + 1):\n",
    "                rdec = [node.val] + rdec\n",
    "                ret = max(ret, len(rdec))\n",
    "            else:\n",
    "                rdec = [node.val]\n",
    "\n",
    "            return ret, linc if len(linc) > len(rinc) else rinc, ldec if len(ldec) > len(rdec) else rdec\n",
    "        \n",
    "        l, x, y = dfs(root)\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.recurse(root)\n",
    "        return self.res\n",
    "\n",
    "    # 返回值4数值含义：node节点(含自身)左侧升降最大长度，node节点右侧(含自身)升降最大长度\n",
    "    def recurse(self, node):\n",
    "        if node is None:\n",
    "            return [0, 0, 0, 0]\n",
    "        curr = [1, 1, 1, 1]\n",
    "        left = self.recurse(node.left)\n",
    "        right = self.recurse(node.right)\n",
    "        if node.left is not None:\n",
    "            if node.val + 1 == node.left.val:\n",
    "                curr[0] = 1 + max(left[0], left[2])\n",
    "            elif node.val - 1 == node.left.val:\n",
    "                curr[1] = 1 + max(left[1], left[3])\n",
    "        if node.right is not None:\n",
    "            if node.val + 1 == node.right.val:\n",
    "                curr[2] = 1 + max(right[0], right[2])\n",
    "            elif node.val - 1 == node.right.val:\n",
    "                curr[3] = 1 + max(right[1], right[3])\n",
    "        self.res = max(self.res, curr[0] + curr[3] - 1, curr[1] + curr[2] - 1)\n",
    "        return curr\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        #TM的树形DP,挺麻烦\n",
    "        ans=0\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            if x is None: return 0,0\n",
    "            cur_up,cur_down=1,1\n",
    "            l_up,l_down=dfs(x.left)\n",
    "            r_up,r_down=dfs(x.right)\n",
    "            l,r=-1,-1\n",
    "            if x.left: l=x.left.val\n",
    "            if x.right: r=x.right.val\n",
    "            if x.val-l==1 and r-x.val==1:\n",
    "                ans=max(ans,l_up+r_down+1)\n",
    "                cur_up=l_up+1\n",
    "                cur_down=r_down+1\n",
    "            elif x.val-r==1 and l-x.val==1:\n",
    "                ans=max(ans,l_down+r_up+1)\n",
    "                cur_up=r_up+1\n",
    "                cur_down=l_down+1\n",
    "            if x.val-l==1:\n",
    "                cur_up=l_up+1\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            elif l-x.val==1:\n",
    "                cur_down=l_down+1\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            if x.val-r==1:\n",
    "                cur_up=max(cur_up,r_up+1)\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            elif r-x.val==1:\n",
    "                cur_down=max(cur_down,r_down+1)\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            else:\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            return cur_up,cur_down\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, [], []\n",
    "\n",
    "            ll, linc, ldec = dfs(node.left)\n",
    "            rl, rinc, rdec = dfs(node.right)\n",
    "\n",
    "            ret = max(ll, rl)\n",
    "            if linc and rdec and node.val == linc[0] - 1 == rdec[0] + 1:\n",
    "                ret = max(ret, len(linc) + 1 + len(rdec))\n",
    "            if rinc and ldec and node.val == rinc[0] - 1 == ldec[0] + 1:\n",
    "                ret = max(ret, len(rinc) + 1 + len(ldec))\n",
    "            if (not linc or node.val == linc[0] - 1):\n",
    "                linc = [node.val] + linc\n",
    "                ret = max(ret, len(linc))\n",
    "            else:\n",
    "                linc = [node.val]\n",
    "            if (not ldec or node.val == ldec[0] + 1):\n",
    "                ldec = [node.val] + ldec\n",
    "                ret = max(ret, len(ldec))\n",
    "            else:\n",
    "                ldec= [node.val]\n",
    "            if (not rinc or node.val == rinc[0] - 1):\n",
    "                rinc = [node.val] + rinc\n",
    "                ret = max(ret, len(rinc))\n",
    "            else:\n",
    "                rinc= [node.val]\n",
    "            if (not rdec or node.val == rdec[0] + 1):\n",
    "                rdec = [node.val] + rdec\n",
    "                ret = max(ret, len(rdec))\n",
    "            else:\n",
    "                rdec = [node.val]\n",
    "\n",
    "            return ret, linc if len(linc) > len(rinc) else rinc, ldec if len(ldec) > len(rdec) else rdec\n",
    "        \n",
    "        l, x, y = dfs(root)\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "      maxLen = 1\n",
    "      def dfs(root):\n",
    "        nonlocal maxLen\n",
    "        if not root:\n",
    "          return 0, 0, 0 # increase len, decrease len, val\n",
    "\n",
    "        LlenUp, LlenDown, Lval = dfs(root.left)\n",
    "        RlenUp, RlenDown, Rval = dfs(root.right)\n",
    "        if root.val - Lval == 1:\n",
    "          if Rval - root.val == 1:\n",
    "            maxLen = max(maxLen, LlenUp + RlenDown + 1)\n",
    "            return LlenUp + 1, RlenDown + 1, root.val\n",
    "          elif root.val - Rval == 1:\n",
    "            maxLen = max(maxLen, LlenUp + 1, RlenUp + 1)\n",
    "            return max(LlenUp, RlenUp) + 1, 1, root.val\n",
    "          else:\n",
    "            maxLen = max(maxLen, LlenUp + 1)\n",
    "            return LlenUp + 1, 1, root.val\n",
    "        elif Lval - root.val == 1:\n",
    "          if root.val - Rval == 1:\n",
    "            maxLen = max(maxLen, LlenDown + RlenUp + 1)\n",
    "            return RlenUp + 1, LlenDown + 1, root.val\n",
    "          elif Rval - root.val == 1:\n",
    "            maxLen = max(maxLen, LlenDown + 1, RlenDown + 1)\n",
    "            return 1, max(LlenDown, RlenDown) + 1, root.val\n",
    "          else:\n",
    "            maxLen = max(maxLen, LlenDown + 1)\n",
    "            return 1, LlenDown + 1, root.val\n",
    "        else:\n",
    "          if root.val - Rval == 1:\n",
    "            maxLen = max(maxLen, RlenUp + 1)\n",
    "            return RlenUp + 1, 1, root.val\n",
    "          elif Rval - root.val == 1:\n",
    "            maxLen = max(maxLen, RlenDown + 1)\n",
    "            return 1, RlenDown + 1, root.val\n",
    "        return 1, 1, root.val\n",
    "      dfs(root)\n",
    "      return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        ret=0\n",
    "        def postorder(root):\n",
    "            if root==None:\n",
    "                return -2,-2\n",
    "            left_up,left_down=postorder(root.left)\n",
    "            right_up,right_down=postorder(root.right)\n",
    "            ret_up,ret_down=0,0\n",
    "            if left_up!=-2 and root.left.val-1==root.val:\n",
    "                ret_up=left_up+1\n",
    "            if right_up!=-2 and root.right.val-1==root.val:\n",
    "                ret_up=max(right_up+1,ret_up)\n",
    "            if left_down!=-2 and root.left.val+1==root.val:\n",
    "                ret_down=left_down+1\n",
    "            if right_down!=-2 and root.right.val+1==root.val:\n",
    "                ret_down=max(right_down+1,ret_down)\n",
    "            nonlocal ret\n",
    "            ret=max(ret_up+ret_down+1,ret)\n",
    "            return ret_up,ret_down\n",
    "        postorder(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "      maxLen = 1\n",
    "      def dfs(root):\n",
    "        nonlocal maxLen\n",
    "        if not root:\n",
    "          return 0, 0, 0 # increase len, decrease len, val\n",
    "\n",
    "        LlenUp, LlenDown, Lval = dfs(root.left)\n",
    "        RlenUp, RlenDown, Rval = dfs(root.right)\n",
    "        if root.val - Lval == 1:\n",
    "          if Rval - root.val == 1:\n",
    "            maxLen = max(maxLen, LlenUp + RlenDown + 1)\n",
    "            return LlenUp + 1, RlenDown + 1, root.val\n",
    "          elif root.val - Rval == 1:\n",
    "            maxLen = max(maxLen, LlenUp + 1, RlenUp + 1)\n",
    "            return max(LlenUp, RlenUp) + 1, 1, root.val\n",
    "          else:\n",
    "            maxLen = max(maxLen, LlenUp + 1)\n",
    "            return LlenUp + 1, 1, root.val\n",
    "        elif Lval - root.val == 1:\n",
    "          if root.val - Rval == 1:\n",
    "            maxLen = max(maxLen, LlenDown + RlenUp + 1)\n",
    "            return RlenUp + 1, LlenDown + 1, root.val\n",
    "          elif Rval - root.val == 1:\n",
    "            maxLen = max(maxLen, LlenDown + 1, RlenDown + 1)\n",
    "            return 1, max(LlenDown, RlenDown) + 1, root.val\n",
    "          else:\n",
    "            maxLen = max(maxLen, LlenDown + 1)\n",
    "            return 1, LlenDown + 1, root.val\n",
    "        else:\n",
    "          if root.val - Rval == 1:\n",
    "            maxLen = max(maxLen, RlenUp + 1)\n",
    "            return RlenUp + 1, 1, root.val\n",
    "          elif Rval - root.val == 1:\n",
    "            maxLen = max(maxLen, RlenDown + 1)\n",
    "            return 1, RlenDown + 1, root.val\n",
    "        return 1, 1, root.val\n",
    "      dfs(root)\n",
    "      return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "      maxLen = 1\n",
    "      def dfs(root):\n",
    "        nonlocal maxLen\n",
    "        if not root:\n",
    "          return 0, 0, 0 # increase len, decrease len, val\n",
    "\n",
    "        LlenUp, LlenDown, Lval = dfs(root.left)\n",
    "        RlenUp, RlenDown, Rval = dfs(root.right)\n",
    "        if root.val - Lval == 1:\n",
    "          if Rval - root.val == 1:\n",
    "            maxLen = max(maxLen, LlenUp + RlenDown + 1)\n",
    "            return LlenUp + 1, RlenDown + 1, root.val\n",
    "          elif root.val - Rval == 1:\n",
    "            maxLen = max(maxLen, LlenUp + 1, RlenUp + 1)\n",
    "            return max(LlenUp, RlenUp) + 1, 1, root.val\n",
    "          else:\n",
    "            maxLen = max(maxLen, LlenUp + 1)\n",
    "            return LlenUp + 1, 1, root.val\n",
    "        elif Lval - root.val == 1:\n",
    "          if root.val - Rval == 1:\n",
    "            maxLen = max(maxLen, LlenDown + RlenUp + 1)\n",
    "            return RlenUp + 1, LlenDown + 1, root.val\n",
    "          elif Rval - root.val == 1:\n",
    "            maxLen = max(maxLen, LlenDown + 1, RlenDown + 1)\n",
    "            return 1, max(LlenDown, RlenDown) + 1, root.val\n",
    "          else:\n",
    "            maxLen = max(maxLen, LlenDown + 1)\n",
    "            return 1, LlenDown + 1, root.val\n",
    "        else:\n",
    "          if root.val - Rval == 1:\n",
    "            maxLen = max(maxLen, RlenUp + 1)\n",
    "            return RlenUp + 1, 1, root.val\n",
    "          elif Rval - root.val == 1:\n",
    "            maxLen = max(maxLen, RlenDown + 1)\n",
    "            return 1, RlenDown + 1, root.val\n",
    "        return 1, 1, root.val\n",
    "      dfs(root)\n",
    "      return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: TreeNode) -> int:\n",
    "        \n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:return (0,0)\n",
    "            l,r=dfs(root.left),dfs(root.right)\n",
    "            asc = desc =1\n",
    "\n",
    "            if root.left:\n",
    "                if root.left.val == root.val+1:\n",
    "                    asc += l[0]\n",
    "                elif root.left.val == root.val-1:\n",
    "                    desc += l[1]\n",
    "            if root.right:\n",
    "                if root.right.val == root.val+1:\n",
    "                    asc = max(asc, r[0]+1)\n",
    "                if root.right.val == root.val-1:\n",
    "                    desc = max(desc, r[1]+1)\n",
    "\n",
    "            res=max(res,asc + desc -1)\n",
    "            return (asc,desc)\n",
    "            \n",
    "        res=0\n",
    "        dfs(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            nonlocal max_len\n",
    "\n",
    "            if not root: return [0, 0]\n",
    "\n",
    "            inc = dec = 1\n",
    "            if root.left:\n",
    "                left = dfs(root.left)\n",
    "                if root.val == root.left.val + 1:\n",
    "                    dec = left[1] + 1\n",
    "                elif root.val == root.left.val - 1:\n",
    "                    inc = left[0] + 1\n",
    "            \n",
    "            if root.right:\n",
    "                right = dfs(root.right)\n",
    "                if root.val == root.right.val + 1:\n",
    "                    dec = max(dec, right[1] + 1)\n",
    "                elif root.val == root.right.val - 1:\n",
    "                    inc = max(inc, right[0] + 1)\n",
    "            \n",
    "            max_len = max(max_len, inc + dec - 1)\n",
    "            return [inc, dec]\n",
    "\n",
    "        \n",
    "        max_len = 0\n",
    "        dfs(root)\n",
    "        return max_len\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 提议没表述清楚，垃圾题目\n",
    "    def longestConsecutive(self, root: TreeNode) -> int:\n",
    "        self.res=0\n",
    "        def postorder(root):\n",
    "            # 后续遍历\n",
    "            if not root:\n",
    "                return 3 * 10**4 + 2, 1, 1\n",
    "            left_val, inc_left, dec_left=postorder(root.left)\n",
    "            right_val, inc_right, dec_right=postorder(root.right)\n",
    "            inc_cur=1\n",
    "            dec_cur=1\n",
    "            if left_val==root.val-1:\n",
    "                inc_cur=max(inc_cur,1+inc_left)\n",
    "            if right_val==root.val-1:\n",
    "                inc_cur=max(inc_cur,1+inc_right)\n",
    "            if left_val==root.val+1:\n",
    "                dec_cur=max(dec_cur,dec_left+1)\n",
    "            if right_val==root.val+1:\n",
    "                dec_cur=max(dec_cur,dec_right+1)\n",
    "            self.res=max(self.res, inc_cur + dec_cur - 1)\n",
    "            return root.val, inc_cur, dec_cur\n",
    "        \n",
    "        postorder(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        #其实是树形DP,每个节点有两个状态\n",
    "        #TM的树形DP,挺麻烦\n",
    "        ans=0\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            if x is None: return 0,0\n",
    "            cur_up,cur_down=1,1\n",
    "            l_up,l_down=dfs(x.left)\n",
    "            r_up,r_down=dfs(x.right)\n",
    "            l,r=-1,-1\n",
    "            if x.left: l=x.left.val\n",
    "            if x.right: r=x.right.val\n",
    "            if x.val-l==1 and r-x.val==1:\n",
    "                ans=max(ans,l_up+r_down+1)\n",
    "                cur_up=l_up+1\n",
    "                cur_down=r_down+1\n",
    "            elif x.val-r==1 and l-x.val==1:\n",
    "                ans=max(ans,l_down+r_up+1)\n",
    "                cur_up=r_up+1\n",
    "                cur_down=l_down+1\n",
    "            if x.val-l==1:\n",
    "                cur_up=l_up+1\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            elif l-x.val==1:\n",
    "                cur_down=l_down+1\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            if x.val-r==1:\n",
    "                cur_up=max(cur_up,r_up+1)\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            elif r-x.val==1:\n",
    "                cur_down=max(cur_down,r_down+1)\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            else:\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            return cur_up,cur_down\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = [1]\n",
    "        def ll(root):\n",
    "            if root is None:\n",
    "                return 0, 0\n",
    "            left_inc, left_dec = ll(root.left)\n",
    "            right_inc, right_dec = ll(root.right)\n",
    "            inc = 1\n",
    "            if root.left and root.left.val - root.val == 1:\n",
    "                inc = max(inc, left_inc + 1)\n",
    "            if root.right and root.right.val - root.val == 1:\n",
    "                inc = max(inc, right_inc + 1)\n",
    "            dec = 1\n",
    "            if root.left and root.val - root.left.val == 1:\n",
    "                dec = max(dec, left_dec + 1)\n",
    "            if root.right and root.val - root.right.val == 1:\n",
    "                dec = max(dec, right_dec + 1)\n",
    "            ans[0] = max(ans[0], inc + dec - 1)\n",
    "\n",
    "            return inc, dec\n",
    "\n",
    "        ll(root)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        self._max_length = 0\n",
    "\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.answer_1(root)\n",
    "\n",
    "    def answer_1(self, root):\n",
    "        self._dfs_1(root)\n",
    "        return self._max_length\n",
    "\n",
    "    def _dfs_1(self, node):\n",
    "        if not node:\n",
    "            return 0, 0\n",
    "        left = self._dfs_1(node.left)\n",
    "        right = self._dfs_1(node.right)\n",
    "\n",
    "        inc = dec = 1\n",
    "        if node.left:\n",
    "            if node.left.val == node.val + 1:\n",
    "                inc += left[0]\n",
    "            elif node.left.val == node.val - 1:\n",
    "                dec += left[1]\n",
    "\n",
    "        if node.right:\n",
    "            if node.right.val == node.val + 1:\n",
    "                inc = max(inc, right[0] +1)\n",
    "            elif node.right.val == node.val - 1:\n",
    "                dec = max(dec, right[1] + 1)\n",
    "        self._max_length = max(self._max_length, dec + inc - 1)\n",
    "        return inc, dec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0,0 #第一位表示以上升序列返回，第二位表示以下降序列返回\n",
    "\n",
    "\n",
    "            nonlocal res\n",
    "            \n",
    "            left_up, left_down = dfs(root.left)\n",
    "            right_up, right_down = dfs(root.right)\n",
    "\n",
    "            up_tmp = 1\n",
    "            down_tmp = 1\n",
    "\n",
    "            #动态规划\n",
    "            if not root.left or root.val-1 == root.left.val:\n",
    "                up_tmp=max(up_tmp,1+left_up)\n",
    "\n",
    "            if not root.right or root.val-1 == root.right.val:\n",
    "                up_tmp=max(up_tmp,1+right_up)\n",
    "\n",
    "            if not root.left or root.val+1 == root.left.val:\n",
    "                down_tmp=max(down_tmp,1+left_down)\n",
    "\n",
    "            if not root.right or root.val+1 == root.right.val:\n",
    "                down_tmp=max(down_tmp,1+right_down)\n",
    "\n",
    "\n",
    "            #输出\n",
    "            if (not root.left or root.val-1 == root.left.val) and (not root.right or root.val+1==root.right.val):\n",
    "                res = max(res,1+left_up+right_down,1)\n",
    "            if (not root.left or root.val+1 == root.left.val) and (not root.right or root.val-1==root.right.val):\n",
    "                res = max(res,1+left_down+right_up,1)\n",
    "            \n",
    "            if not root.left or root.val+1 == root.left.val:\n",
    "                res = max(res,1+left_down)\n",
    "            if not root.left or root.val-1 == root.left.val:\n",
    "                res = max(res,1+left_up)\n",
    "\n",
    "            if not root.right or root.val+1 == root.right.val:\n",
    "                res = max(res,1+right_down)\n",
    "\n",
    "            if not root.right or root.val-1 == root.right.val:\n",
    "                res = max(res,1+right_up)\n",
    "            \n",
    "            return up_tmp,down_tmp\n",
    "\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, [], []\n",
    "\n",
    "            ll, linc, ldec = dfs(node.left)\n",
    "            rl, rinc, rdec = dfs(node.right)\n",
    "\n",
    "            ret = max(ll, rl)\n",
    "            if linc and rdec and node.val == linc[0] - 1 == rdec[0] + 1:\n",
    "                ret = max(ret, len(linc) + 1 + len(rdec))\n",
    "            elif rinc and ldec and node.val == rinc[0] - 1 == ldec[0] + 1:\n",
    "                ret = max(ret, len(rinc) + 1 + len(ldec))\n",
    "            if (not linc or node.val == linc[0] - 1):\n",
    "                linc = [node.val] + linc\n",
    "            else:\n",
    "                linc = [node.val]\n",
    "            if (not ldec or node.val == ldec[0] + 1):\n",
    "                ldec = [node.val] + ldec\n",
    "            else:\n",
    "                ldec= [node.val]\n",
    "            if (not rinc or node.val == rinc[0] - 1):\n",
    "                rinc = [node.val] + rinc\n",
    "            else:\n",
    "                rinc= [node.val]\n",
    "            if (not rdec or node.val == rdec[0] + 1):\n",
    "                rdec = [node.val] + rdec\n",
    "            else:\n",
    "                rdec = [node.val]\n",
    "\n",
    "            return max(ret, len(linc), len(ldec), len(rinc), len(rdec)), linc if len(linc) > len(rinc) else rinc, ldec if len(ldec) > len(rdec) else rdec\n",
    "        \n",
    "        l, x, y = dfs(root)\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def longestConsecutive(self, root: TreeNode) -> int:\n",
    "               \n",
    "       def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "       maxval = 0\n",
    "       longest_path(root)\n",
    "       return maxval\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return [0,0]\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            ans = [1,1]\n",
    "            if root.left:\n",
    "                if root.left.val - root.val == -1:\n",
    "                    ans[0]  = l[0]+1\n",
    "                elif root.left.val - root.val == 1:\n",
    "                    ans[1] = l[1]+1\n",
    "            if root.right:\n",
    "                if root.right.val - root.val == -1:\n",
    "                    ans[0]  = max(r[0]+1,ans[0])\n",
    "                elif root.right.val - root.val == 1:\n",
    "                    ans[1] = max(r[1]+1,ans[1])\n",
    "            res = max(res,ans[0]+ans[1]-1)\n",
    "            return ans\n",
    "\n",
    "        res = 0\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "   def longestConsecutive(self, root: TreeNode) -> int:\n",
    "               \n",
    "       def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "       maxval = 0\n",
    "       longest_path(root)\n",
    "       return maxval\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        #TM的树形DP,挺麻烦\n",
    "        ans=0\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            if x is None: return 0,0\n",
    "            cur_up,cur_down=1,1\n",
    "            l_up,l_down=dfs(x.left)\n",
    "            r_up,r_down=dfs(x.right)\n",
    "            l,r=-1,-1\n",
    "            if x.left: l=x.left.val\n",
    "            if x.right: r=x.right.val\n",
    "            if x.val-l==1 and r-x.val==1:\n",
    "                ans=max(ans,l_up+r_down+1)\n",
    "                cur_up=l_up+1\n",
    "                cur_down=r_down+1\n",
    "            elif x.val-r==1 and l-x.val==1:\n",
    "                ans=max(ans,l_down+r_up+1)\n",
    "                cur_up=r_up+1\n",
    "                cur_down=l_down+1\n",
    "            if x.val-l==1:\n",
    "                cur_up=l_up+1\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            elif l-x.val==1:\n",
    "                cur_down=l_down+1\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            if x.val-r==1:\n",
    "                cur_up=max(cur_up,r_up+1)\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            elif r-x.val==1:\n",
    "                cur_down=max(cur_down,r_down+1)\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            else:\n",
    "                ans=max(ans,cur_down,cur_up)\n",
    "            return cur_up,cur_down\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            left_inc, left_dec = dfs(node.left)\n",
    "            right_inc, right_dec = dfs(node.right)\n",
    "            inc, dec = 1, 1\n",
    "            if left_inc > 0 and node.val == node.left.val + 1:\n",
    "                inc = left_inc + 1\n",
    "            if left_dec > 0 and node.val == node.left.val - 1:\n",
    "                dec = left_dec + 1\n",
    "            if right_inc > 0 and node.val == node.right.val + 1:\n",
    "                inc = max(inc, right_inc + 1)\n",
    "            if right_dec > 0 and node.val == node.right.val - 1:\n",
    "                dec = max(dec, right_dec + 1)\n",
    "            self.max_length = max(self.max_length, inc + dec - 1)\n",
    "            return inc, dec\n",
    "\n",
    "        self.max_length = 1\n",
    "        dfs(root)\n",
    "        return self.max_length\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(root: TreeNode) -> int:\n",
    "            if not root: return [0,0]\n",
    "            nonlocal ans\n",
    "            status = [1]*2\n",
    "\n",
    "            leftStatus = dfs(root.left)\n",
    "            rightStatus = dfs(root.right)\n",
    "\n",
    "            if root.left:\n",
    "                if root.left.val + 1 == root.val:\n",
    "                    status[0] = leftStatus[0] + 1\n",
    "                elif root.left.val - 1 == root.val:\n",
    "                    status[1] = leftStatus[1] + 1\n",
    "\n",
    "            if root.right:\n",
    "                if root.right.val + 1 == root.val:\n",
    "                    status[0] = max(status[0], rightStatus[0] + 1)\n",
    "                elif root.right.val - 1 == root.val:\n",
    "                    status[1] = max(status[1], rightStatus[1] + 1)\n",
    "\n",
    "            ans = max(ans, status[0] + status[1] - 1)\n",
    "            return status\n",
    "\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node: TreeNode) -> (int, int):\n",
    "            icr = dcr = 1\n",
    "            if node.left:\n",
    "                l_icr, l_dcr = dfs(node.left)\n",
    "                if node.left.val + 1 == node.val:\n",
    "                    icr = l_icr + 1\n",
    "                if node.left.val - 1 == node.val:\n",
    "                    dcr = l_dcr + 1\n",
    "            if node.right:\n",
    "                r_icr, r_dcr = dfs(node.right)\n",
    "                if node.right.val + 1 == node.val:\n",
    "                    icr = max(icr, r_icr + 1)\n",
    "                if node.right.val - 1 == node.val:\n",
    "                    dcr = max(dcr, r_dcr + 1)\n",
    "            nonlocal ans\n",
    "            ans = max(ans, icr + dcr - 1)\n",
    "            return (icr, dcr)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        maxnum=0\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0,0\n",
    "            l1,l2=dfs(root.left)\n",
    "            r1,r2=dfs(root.right)\n",
    "            if root.left and root.val!=root.left.val-1:\n",
    "                l1=0\n",
    "            if root.right and root.val!=root.right.val-1:\n",
    "                r1=0\n",
    "            if root.left and root.val!=root.left.val+1:\n",
    "                l2=0\n",
    "            if root.right and root.val!=root.right.val+1:\n",
    "                r2=0\n",
    "            nonlocal maxnum\n",
    "            maxnum=max(maxnum,max(l1,r1)+max(l2,r2)+1)\n",
    "            return max(l1,r1)+1,max(l2,r2)+1\n",
    "        dfs(root)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0,0 #第一位表示以上升序列返回，第二位表示以下降序列返回\n",
    "\n",
    "\n",
    "            nonlocal res\n",
    "            \n",
    "            left_up, left_down = dfs(root.left)\n",
    "            right_up, right_down = dfs(root.right)\n",
    "\n",
    "            up_tmp = 1\n",
    "            down_tmp = 1\n",
    "\n",
    "            #动态规划\n",
    "            if not root.left or root.val-1 == root.left.val:\n",
    "                up_tmp=max(up_tmp,1+left_up)\n",
    "\n",
    "            if not root.right or root.val-1 == root.right.val:\n",
    "                up_tmp=max(up_tmp,1+right_up)\n",
    "\n",
    "            if not root.left or root.val+1 == root.left.val:\n",
    "                down_tmp=max(down_tmp,1+left_down)\n",
    "\n",
    "            if not root.right or root.val+1 == root.right.val:\n",
    "                down_tmp=max(down_tmp,1+right_down)\n",
    "\n",
    "\n",
    "            #输出\n",
    "            if (not root.left or root.val-1 == root.left.val) and (not root.right or root.val+1==root.right.val):\n",
    "                res = max(res,1+left_up+right_down,1)\n",
    "            if (not root.left or root.val+1 == root.left.val) and (not root.right or root.val-1==root.right.val):\n",
    "                res = max(res,1+left_down+right_up,1)\n",
    "            \n",
    "            if not root.left or root.val+1 == root.left.val:\n",
    "                res = max(res,1+left_down)\n",
    "            if not root.left or root.val-1 == root.left.val:\n",
    "                res = max(res,1+left_up)\n",
    "\n",
    "            if not root.right or root.val+1 == root.right.val:\n",
    "                res = max(res,1+right_down)\n",
    "\n",
    "            if not root.right or root.val-1 == root.right.val:\n",
    "                res = max(res,1+right_up)\n",
    "            \n",
    "            return up_tmp,down_tmp\n",
    "\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def longestConsecutive(self, root: TreeNode) -> int:\n",
    "               \n",
    "       def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "       maxval = 0\n",
    "       longest_path(root)\n",
    "       return maxval\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Info:\n",
    "    def __init__(self,val=-1,up=0,down=0):\n",
    "        self.val = val\n",
    "        self.up = up # 从下往上升\n",
    "        self.down = down # 从下往上降\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 1\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if node is None:\n",
    "                return Info()\n",
    "            if node.left is None and node.right is None:\n",
    "                return Info(node.val,1,1)\n",
    "            u,d = 1,1\n",
    "            leftI, rightI = dfs(node.left), dfs(node.right)\n",
    "            if node.val == leftI.val + 1:\n",
    "                u = max(u, leftI.up + 1)\n",
    "            if node.val == rightI.val + 1:\n",
    "                u = max(u, rightI.up + 1)\n",
    "            if node.val == leftI.val - 1:\n",
    "                d = max(d, leftI.down + 1)\n",
    "            if node.val == rightI.val - 1:\n",
    "                d = max(d, rightI.down + 1)\n",
    "            res = max(res,u, d)\n",
    "            if leftI.val + 1 == node.val == rightI.val - 1:\n",
    "                res = max(res, leftI.up + rightI.down + 1)\n",
    "            if leftI.val - 1 == node.val == rightI.val + 1:\n",
    "                res = max(res, leftI.down + rightI.up + 1)\n",
    "            print(node.val, u,d)\n",
    "            return Info(node.val, u, d)\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        # 注意题中描述，还可以是子-父-子的关系\n",
    "        self.res = 1\n",
    "        def dfs(p):\n",
    "            res1, res2 = 1, 1\n",
    "            if p.left:\n",
    "                t1, t2 = dfs(p.left)\n",
    "                res1 = 1+(t1 if p.left.val == p.val +1 else 0)\n",
    "                res2 = 1+(t2 if p.left.val == p.val -1 else 0)\n",
    "            if p.right:\n",
    "                t1, t2 = dfs(p.right)\n",
    "                t1 = 1 + (t1 if p.right.val == p.val + 1 else 0)\n",
    "                t2 = 1 + (t2 if p.right.val == p.val - 1 else 0)\n",
    "                res1 = max(res1, t1)\n",
    "                res2 = max(res2, t2)\n",
    "            self.res = max(self.res, res1+res2-1)\n",
    "            return res1, res2\n",
    "        dfs(root)\n",
    "        return self.res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        ans=-1\n",
    "        def bl(p):\n",
    "            nonlocal ans\n",
    "            ans=max(ans,f1(p)+f2(p)-1)\n",
    "            if p.left:\n",
    "                bl(p.left)\n",
    "            if p.right:\n",
    "                bl(p.right)\n",
    "        @cache\n",
    "        def f1(p):\n",
    "            if p is None:\n",
    "                return 0\n",
    "            t=1\n",
    "            if p.left and p.left.val==p.val+1:\n",
    "                t=max(t,f1(p.left)+1)\n",
    "            if p.right and p.right.val==p.val+1:\n",
    "                t=max(t,f1(p.right)+1)\n",
    "            return t\n",
    "        def f2(p): \n",
    "            if p is None:\n",
    "                return 0\n",
    "            t=1\n",
    "            if p.left and p.left.val==p.val-1:\n",
    "                t=max(t,f2(p.left)+1)\n",
    "            if p.right and p.right.val==p.val-1:\n",
    "                t=max(t,f2(p.right)+1)\n",
    "            return t\n",
    "        bl(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def longestConsecutive(self, root: TreeNode) -> int:\n",
    "               \n",
    "       def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "       maxval = 0\n",
    "       longest_path(root)\n",
    "       return maxval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def longestConsecutive(self, root: TreeNode) -> int:\n",
    "               \n",
    "       def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "       maxval = 0\n",
    "       longest_path(root)\n",
    "       return maxval\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(root:TreeNode) -> List[int]:\n",
    "            nonlocal maxval\n",
    "\n",
    "            if(root==None):\n",
    "                return [0,0]\n",
    "            inc=des=1\n",
    "            if(root.left):\n",
    "                left=dfs(root.left)\n",
    "                if(root.val==root.left.val+1):\n",
    "                    des=left[1]+1\n",
    "                elif(root.val==root.left.val-1):\n",
    "                    inc=left[0]+1\n",
    "\n",
    "            if(root.right):\n",
    "                right=dfs(root.right)\n",
    "                if(root.val==root.right.val+1):\n",
    "                    des=max(right[1]+1,des)\n",
    "                elif(root.val==root.right.val-1):\n",
    "                    inc=max(right[0]+1,inc)\n",
    "            maxval=max(maxval,inc+des-1)\n",
    "\n",
    "            return [inc,des]\n",
    "        maxval=0\n",
    "        dfs(root)\n",
    "        return maxval\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def longestConsecutive(self, root: TreeNode) -> int:\n",
    "               \n",
    "       def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "       maxval = 0\n",
    "       longest_path(root)\n",
    "       return maxval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        def longest_path(root: TreeNode) -> List[int]:\n",
    "            nonlocal maxval\n",
    "\n",
    "            if not root:\n",
    "                return [0,0]\n",
    "            \n",
    "            inr = dcr = 1\n",
    "            if root.left:\n",
    "                left = longest_path(root.left)\n",
    "                if root.val == root.left.val+1:\n",
    "                    dcr = left[1] +1\n",
    "                elif root.val == root.left.val-1:\n",
    "                    inr = left[0]+1\n",
    "            \n",
    "            if root.right:\n",
    "                right = longest_path(root.right)\n",
    "                if root.val == root.right.val+1:\n",
    "                    dcr = max(dcr, right[1] +1)\n",
    "                elif root.val == root.right.val-1:\n",
    "                    inr = max(inr, right[0]+1)\n",
    "            maxval = max(maxval,dcr+inr-1)\n",
    "            return [inr,dcr]\n",
    "\n",
    "        maxval = 0\n",
    "        longest_path(root)\n",
    "        return maxval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res=0\n",
    "        def postorder(root):\n",
    "\n",
    "            if not root:\n",
    "                return None,0,0\n",
    "            v1,i1,d1=postorder(root.left)\n",
    "            v2,i2,d2=postorder(root.right)\n",
    "            i0=0\n",
    "            d0=0\n",
    "            v=root.val\n",
    "            if v1==v-1:\n",
    "                i0=max(i0,1+i1)\n",
    "            if v2==v-1:\n",
    "                i0=max(i0,1+i2)\n",
    "            if v1==v+1:\n",
    "                d0=max(d0,d1+1)\n",
    "            if v2==v+1:\n",
    "                d0=max(d0,d2+1)\n",
    "\n",
    "            self.res=max(self.res,1+i0+d0)\n",
    "            return root.val,i0,d0\n",
    "        postorder(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.res = 1\n",
    "        def dfs(root):\n",
    "            if not root: return (0, 0)\n",
    "            left, right = dfs(root.left), dfs(root.right)\n",
    "            inc = dec = 1\n",
    "            if root.left:\n",
    "                if root.left.val == root.val + 1:\n",
    "                    inc += left[0]\n",
    "                elif root.left.val == root.val - 1:\n",
    "                    dec += left[1]\n",
    "            if root.right:\n",
    "                if root.right.val == root.val + 1:\n",
    "                    inc = max(inc, right[0] + 1)\n",
    "                elif root.right.val == root.val - 1:\n",
    "                    dec = max(dec, right[1] + 1)\n",
    "            \n",
    "            self.res = max(self.res, inc + dec - 1)\n",
    "            return (inc, dec)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        def longest_path(root: TreeNode) -> List[int]:\n",
    "           nonlocal maxval\n",
    "           \n",
    "           if not root:\n",
    "               return [0, 0]\n",
    "           \n",
    "           inr = dcr = 1\n",
    "           if root.left:\n",
    "               left = longest_path(root.left)\n",
    "               if (root.val == root.left.val + 1):\n",
    "                   dcr = left[1] + 1\n",
    "               elif (root.val == root.left.val - 1):\n",
    "                   inr = left[0] + 1\n",
    "           \n",
    "           if root.right:\n",
    "               right = longest_path(root.right)\n",
    "               if (root.val == root.right.val + 1):\n",
    "                   dcr = max(dcr, right[1] + 1)\n",
    "               elif (root.val == root.right.val - 1):\n",
    "                   inr = max(inr, right[0] + 1)\n",
    "                   \n",
    "           maxval = max(maxval, dcr + inr - 1)\n",
    "           return [inr, dcr]\n",
    "       \n",
    "        maxval = 0\n",
    "        longest_path(root)\n",
    "        return maxval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return (0,0)\n",
    "            l, d = 1, 1\n",
    "            if root.left:\n",
    "                ll, ld = dfs(root.left)\n",
    "                if root.left.val == root.val + 1:\n",
    "                    l = ll + 1\n",
    "                elif root.left.val == root.val - 1:\n",
    "                    d = ld + 1\n",
    "            if root.right:\n",
    "                rl, rd = dfs(root.right)\n",
    "                if root.right.val == root.val + 1:\n",
    "                    l = max(l, rl + 1)\n",
    "                elif root.right.val == root.val - 1:\n",
    "                    d = max(d, rd + 1)\n",
    "            self.res = max(self.res, l + d - 1)\n",
    "            return (l , d)\n",
    "        dfs(root)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal ans\n",
    "\n",
    "            if node is None:\n",
    "                return 100000000, 0, 0\n",
    "\n",
    "            b_asc_len = 1\n",
    "            b_dsc_len = 1\n",
    "\n",
    "            lval, l_asc_len, l_dsc_len = dfs(node.left)\n",
    "            rval, r_asc_len, r_dsc_len = dfs(node.right)\n",
    "\n",
    "            if lval + 1 == node.val:\n",
    "                b_asc_len = max(b_asc_len, l_asc_len + 1)\n",
    "            if node.val + 1 == rval:\n",
    "                b_dsc_len = max(b_dsc_len, r_dsc_len + 1)\n",
    "\n",
    "            if rval + 1 == node.val:\n",
    "                b_asc_len = max(b_asc_len, 1 + r_asc_len)\n",
    "            if node.val + 1 == lval:\n",
    "                b_dsc_len = max(b_dsc_len, 1 + l_dsc_len)\n",
    "\n",
    "            ans = max(ans, b_asc_len + b_dsc_len - 1)\n",
    "            return (node.val, b_asc_len, b_dsc_len)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        def longestPath(node: TreeNode) -> List[int]:\n",
    "            if not node:\n",
    "                return [0, 0]\n",
    "\n",
    "            inc = dec = 1\n",
    "            if node.left:\n",
    "                left = longestPath(node.left)\n",
    "                if node.val == node.left.val + 1:\n",
    "                    dec = left[1] + 1\n",
    "                elif node.val == node.left.val - 1:\n",
    "                    inc = left[0] + 1\n",
    "            \n",
    "            if node.right:\n",
    "                right = longestPath(node.right)\n",
    "                if node.val == node.right.val + 1:\n",
    "                    dec = max(dec, right[1] + 1)\n",
    "                elif node.val == node.right.val - 1:\n",
    "                    inc = max(inc, right[0] + 1)\n",
    "            \n",
    "            nonlocal max_val\n",
    "            max_val = max(max_val, inc + dec - 1)\n",
    "            return [inc, dec]\n",
    "        \n",
    "        max_val = 0\n",
    "        longestPath(root)\n",
    "        return max_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        mapping = dict()\n",
    "        def dfs(node: Optional[TreeNode]):\n",
    "            nonlocal mapping, ans\n",
    "            if node.left:\n",
    "                mapping[node.left] = node\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                mapping[node.right] = node\n",
    "                dfs(node.right)\n",
    "            ans = max(ans, bfs(node, -1) + bfs(node, 1) + 1) \n",
    "        \n",
    "        def bfs(root: Optional[TreeNode], offset: int) -> int:\n",
    "            nonlocal mapping\n",
    "            start = target = root.val\n",
    "            queue = deque([root])\n",
    "            \n",
    "            while queue:\n",
    "                flag = False\n",
    "                for _ in range(len(queue)):\n",
    "                    next = queue.popleft()\n",
    "                    if next.left and next.left.val == target + offset:\n",
    "                        queue.append(next.left)\n",
    "                        flag = True\n",
    "                    if next.right and next.right.val == target + offset:\n",
    "                        queue.append(next.right)\n",
    "                        flag = True\n",
    "                    if next in mapping and  mapping[next].val == target + offset:\n",
    "                        queue.append(mapping[next])\n",
    "                        flag = True\n",
    "                if flag:\n",
    "                    target += offset\n",
    "            return abs(target - start)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.dfs(root)[0]\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return 0, 0, 0\n",
    "        left_lcs, left_inc, left_des = self.dfs(root.left)\n",
    "        right_lcs, right_inc, right_des = self.dfs(root.right)\n",
    "        \n",
    "        inc = 1\n",
    "        if root.left and root.left.val == root.val + 1:\n",
    "            inc = max(inc, left_inc + 1)\n",
    "        if root.right and root.right.val == root.val + 1:\n",
    "            inc = max(inc, right_inc + 1)\n",
    "        \n",
    "        des = 1\n",
    "        if root.left and root.left.val == root.val - 1:\n",
    "            des = max(des, left_des + 1)\n",
    "        if root.right and root.right.val == root.val - 1:\n",
    "            des = max(des, right_des + 1)\n",
    "            \n",
    "        cur_lcs = max(left_lcs, right_lcs, inc + des - 1)\n",
    "        \n",
    "        return cur_lcs, inc, des\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Info:\n",
    "    def __init__(self,val=-1,up=0,down=0):\n",
    "        self.val = val\n",
    "        self.up = up # 从下往上升\n",
    "        self.down = down # 从下往上降\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 1\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if node is None:\n",
    "                return Info()\n",
    "            u,d = 1,1\n",
    "            leftI, rightI = dfs(node.left), dfs(node.right)\n",
    "            if node.val == leftI.val + 1:\n",
    "                u = max(u, leftI.up + 1)\n",
    "            if node.val == rightI.val + 1:\n",
    "                u = max(u, rightI.up + 1)\n",
    "            if node.val == leftI.val - 1:\n",
    "                d = max(d, leftI.down + 1)\n",
    "            if node.val == rightI.val - 1:\n",
    "                d = max(d, rightI.down + 1)\n",
    "            res = max(res,u, d)\n",
    "            if leftI.val + 1 == node.val == rightI.val - 1:\n",
    "                res = max(res, leftI.up + rightI.down + 1)\n",
    "            if leftI.val - 1 == node.val == rightI.val + 1:\n",
    "                res = max(res, leftI.down + rightI.up + 1)\n",
    "            return Info(node.val, u, d)\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "\n",
    "            leftInc, leftDec, rightInc, rightDec = 0, 0, 0, 0\n",
    "\n",
    "            if root.left:\n",
    "                if root.left.val == root.val - 1:\n",
    "                    leftInc = l[0] + 1\n",
    "                if root.left.val == root.val + 1:\n",
    "                    leftDec = l[1] + 1\n",
    "\n",
    "            if root.right:\n",
    "                if root.right.val == root.val - 1:\n",
    "                    rightInc = r[0] + 1\n",
    "                if root.right.val == root.val + 1:\n",
    "                    rightDec = r[1] + 1\n",
    "            \n",
    "            cur = max(1 + leftDec + rightInc, 1 + leftInc + rightDec)\n",
    "            self.ans = max(self.ans, cur)\n",
    "            return (max(leftInc, rightInc), max(leftDec, rightDec))\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root: return None, 0, 0\n",
    "            v1, l1, r1 = dfs(root.left)\n",
    "            v2, l2, r2 = dfs(root.right)\n",
    "            l, r = 0, 0\n",
    "            v = root.val\n",
    "            if v1 == v - 1:\n",
    "                l = max(l, l1 + 1)\n",
    "            if v2 == v - 1:\n",
    "                l = max(l, l2 + 1)\n",
    "            if v1 == v + 1:\n",
    "                r = max(r, r1 + 1)\n",
    "            if v2 == v + 1:\n",
    "                r = max(r, r2 + 1)\n",
    "            ans = max(ans, 1 + l + r)\n",
    "            return root.val, l, r\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        self.max_len = 1\n",
    "        self.help(root)\n",
    "        return self.max_len\n",
    "\n",
    "    def help(self, node):\n",
    "        if node is None:\n",
    "            return 0,0,0,0,0\n",
    "        if node.left is None and node.right is None:\n",
    "            return 1,1,1,1,1\n",
    "\n",
    "        curve,l_up,l_down,r_up,r_down = 1,1,1,1,1\n",
    "        l_curve,ll_up,ll_down,lr_up,lr_down = self.help(node.left)\n",
    "        r_curve,rl_up,rl_down,rr_up,rr_down = self.help(node.right)\n",
    "\n",
    "        if node.left is None:\n",
    "            if node.val == node.right.val + 1:\n",
    "                r_down = 1+max(rl_down, rr_down)\n",
    "            elif node.val == node.right.val - 1:\n",
    "                r_up = 1+max(rl_up, rr_up)\n",
    "\n",
    "        elif node.right is None:\n",
    "            if node.val == node.left.val + 1:\n",
    "                l_down = 1+max(ll_down, lr_down)\n",
    "            elif node.val == node.left.val - 1:\n",
    "                l_up = 1+max(ll_up, lr_up)\n",
    "\n",
    "        else:\n",
    "            if node.val == node.left.val - 1:\n",
    "                l_up = 1+max(ll_up, lr_up)\n",
    "            elif node.val == node.left.val + 1:\n",
    "                l_down = 1+max(ll_down,lr_down)\n",
    "            if node.val == node.right.val - 1:\n",
    "                r_up = 1 + max(rl_up, rr_up)\n",
    "            elif node.val == node.right.val + 1:\n",
    "                r_down = 1 + max(rl_down, rr_down)\n",
    "            if node.val==node.left.val+1 and node.val==node.right.val-1:\n",
    "                curve = max(curve, 1+max(ll_down,lr_down)+max(rl_up,rr_up))\n",
    "            elif node.val==node.left.val-1 and node.val==node.right.val+1:\n",
    "                curve = max(curve, 1+max(ll_up,lr_up)+max(rl_down, rr_down))\n",
    "        \n",
    "        self.max_len = max([self.max_len, curve, l_up,l_down,r_up,r_down])\n",
    "        return curve,l_up,l_down,r_up,r_down"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        self.max_len = 1\n",
    "        self.help(root)\n",
    "        return self.max_len\n",
    "\n",
    "    def help(self, node):\n",
    "        # 该节点的：弯折最长连续长度，降序最长连续长度，升序最长连续长度。（从上往下看升序降序）\n",
    "        # 弯,左升，左降，右升，右降的长度\n",
    "        if node is None:\n",
    "            return 0,0,0,0,0\n",
    "        if node.left is None and node.right is None:\n",
    "            return 1,1,1,1,1\n",
    "\n",
    "        curve,l_up,l_down,r_up,r_down = 1,1,1,1,1\n",
    "        l_curve,ll_up,ll_down,lr_up,lr_down = self.help(node.left)\n",
    "        r_curve,rl_up,rl_down,rr_up,rr_down = self.help(node.right)\n",
    "\n",
    "        if node.left is None:\n",
    "            if node.val == node.right.val + 1:\n",
    "                r_down = 1+max(rl_down, rr_down)\n",
    "            elif node.val == node.right.val - 1:\n",
    "                r_up = 1+max(rl_up, rr_up)\n",
    "\n",
    "        elif node.right is None:\n",
    "            if node.val == node.left.val + 1:\n",
    "                l_down = 1+max(ll_down, lr_down)\n",
    "            elif node.val == node.left.val - 1:\n",
    "                l_up = 1+max(ll_up, lr_up)\n",
    "\n",
    "        else:\n",
    "            if node.val == node.left.val - 1:\n",
    "                l_up = 1+max(ll_up, lr_up)\n",
    "            elif node.val == node.left.val + 1:\n",
    "                l_down = 1+max(ll_down,lr_down)\n",
    "            if node.val == node.right.val - 1:\n",
    "                r_up = 1 + max(rl_up, rr_up)\n",
    "            elif node.val == node.right.val + 1:\n",
    "                r_down = 1 + max(rl_down, rr_down)\n",
    "            if node.val==node.left.val+1 and node.val==node.right.val-1:\n",
    "                curve = max(curve, 1+max(ll_down,lr_down)+max(rl_up,rr_up))\n",
    "            elif node.val==node.left.val-1 and node.val==node.right.val+1:\n",
    "                curve = max(curve, 1+max(ll_up,lr_up)+max(rl_down, rr_down))\n",
    "        \n",
    "        self.max_len = max([self.max_len, curve, l_up,l_down,r_up,r_down])\n",
    "        return curve,l_up,l_down,r_up,r_down"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        # 多层递归\n",
    "        def dfs_inc(node):\n",
    "            left, right = 0, 0\n",
    "            if node.left and node.left.val == node.val + 1:\n",
    "                left = dfs_inc(node.left)\n",
    "            if node.right and node.right.val == node.val + 1:\n",
    "                right = dfs_inc(node.right)\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        def dfs_desc(node):\n",
    "            left, right = 0, 0\n",
    "            if node.left and node.left.val == node.val - 1:\n",
    "                left = dfs_desc(node.left)\n",
    "            if node.right and node.right.val == node.val - 1:\n",
    "                right = dfs_desc(node.right)\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        def dfs(node):\n",
    "            return dfs_inc(node) + dfs_desc(node) - 1\n",
    "    \n",
    "        if not root: return 0\n",
    "        return max(dfs(root), self.longestConsecutive(root.left), self.longestConsecutive(root.right))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        # 递归\n",
    "        def dfs_inc(node):\n",
    "            left, right = 0, 0\n",
    "            if node.left and node.left.val == node.val + 1:\n",
    "                left = dfs_inc(node.left)\n",
    "            if node.right and node.right.val == node.val + 1:\n",
    "                right = dfs_inc(node.right)\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        def dfs_desc(node):\n",
    "            left, right = 0, 0\n",
    "            if node.left and node.left.val == node.val - 1:\n",
    "                left = dfs_desc(node.left)\n",
    "            if node.right and node.right.val == node.val - 1:\n",
    "                right = dfs_desc(node.right)\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        def dfs(node):\n",
    "            return dfs_inc(node) + dfs_desc(node) - 1\n",
    "    \n",
    "        if not root: return 0\n",
    "        return max(dfs(root), self.longestConsecutive(root.left), self.longestConsecutive(root.right))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        # 递归\n",
    "        def dfs_inc(node):\n",
    "            left, right = 0, 0\n",
    "            if node.left and node.left.val == node.val + 1:\n",
    "                left = dfs_inc(node.left)\n",
    "            if node.right and node.right.val == node.val + 1:\n",
    "                right = dfs_inc(node.right)\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        def dfs_dec(node):\n",
    "            left, right = 0, 0\n",
    "            if node.left and node.left.val == node.val - 1:\n",
    "                left = dfs_dec(node.left)\n",
    "            if node.right and node.right.val == node.val - 1:\n",
    "                right = dfs_dec(node.right)\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        def dfs(node):\n",
    "            return dfs_inc(node) + dfs_dec(node) - 1\n",
    "    \n",
    "        if not root: return 0\n",
    "        return max(dfs(root), self.longestConsecutive(root.left), self.longestConsecutive(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def longestConsecutive(self, root: Optional[TreeNode]) -> int:\n",
    "        # 多层递归\n",
    "        def dfs_inc(node):\n",
    "            left, right = 0, 0\n",
    "            if node.left and node.left.val == node.val + 1:\n",
    "                left = dfs_inc(node.left)\n",
    "            if node.right and node.right.val == node.val + 1:\n",
    "                right = dfs_inc(node.right)\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        def dfs_desc(node):\n",
    "            left, right = 0, 0\n",
    "            if node.left and node.left.val == node.val - 1:\n",
    "                left = dfs_desc(node.left)\n",
    "            if node.right and node.right.val == node.val - 1:\n",
    "                right = dfs_desc(node.right)\n",
    "            return max(left, right) + 1\n",
    "\n",
    "        def dfs(node):\n",
    "            return dfs_inc(node) + dfs_desc(node) - 1\n",
    "    \n",
    "        if not root: return 0\n",
    "        \n",
    "        return max(dfs(root), self.longestConsecutive(root.left), self.longestConsecutive(root.right))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
